package com.wrial.offer;
/*
 * @Author  Wrial
 * @Date Created in 20:15 2020/4/1
 * @Description  和为s的连续正数序列
 *
 * 因为是连续的正整数序列，所以就可以使用滑动窗口来解决这个问题
 */

import java.util.ArrayList;
import java.util.List;

public class FaceTest_57_II {


    // 如果输入一个target，它的连续正数序列的两个值一定不会同时大于它的一半
    // 可以使用俩个指针控制滑动窗口的大小，并且指针只能向右边移动
    public int[][] findContinuousSequence(int target) {
        List<int[]> ans = new ArrayList<>();
        // 滑动窗口的终止条件 pRight=target
        int pLeft = 1;
        int pRight = 1;
        int currentSum = 0;
        while (pLeft <= target / 2) {
            // 如果窗口内的值小于target
            if (currentSum < target) {
                currentSum += pRight;
                pRight++;
            // 如果窗口内的值大于target，就从值小的那边（就是左边）进行移除
            } else if (currentSum > target) {
                currentSum -= pLeft;
                pLeft++;
            // 如果相等就放入list，并且左边界向右移动
            } else {
                int[] temp = new int[pRight - pLeft];
                for (int i = pLeft; i < temp.length + pLeft; i++) {
                    temp[i - pLeft] = i;
                }
                currentSum -= pLeft;
                pLeft++;
                ans.add(temp);
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}
